package fun.coding.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class PalindromePartitioning {

	public static void main(String[] args) {
		PalindromePartitioning ins = new PalindromePartitioning();
		List<List<String>> res1 = ins.partition("aab");
		LeetCodeHelpers.printListOfList(res1);
		/*
		List<List<String>> res2 = ins.partition("aaa");
		LeetCodeHelpers.printListOfList(res2);
		*/
	}
	
	public List<List<String>> partition(String s) {
		List<List<String>> res = new LinkedList<List<String>>();
		
		if (s == null || s.length() == 0) return res;
		
		List<String> cur = new LinkedList<String>();
		helper(0, s, cur, res);
		return res;
	}
	
	private void helper(int start, String s, List<String> cur, List<List<String>> res) {
		// The return condition
		if (start == s.length()) {
			res.add(new LinkedList<String>(cur));
			return;
		}
		
		// This is a very typical recursion pattern
		for (int i = start; i < s.length(); i++) {
			if (!this.isPalindrome(s.substring(start, i + 1))) continue;
			
			cur.add(s.substring(start, i + 1));
			helper(i + 1, s, cur, res);
			cur.remove(cur.size() - 1);	
		}
	}
	
	private Map<String, Boolean> lookup = new HashMap<String, Boolean>();
	
	private boolean isPalindrome(String s) {
		if (lookup.containsKey(s)) {
			return lookup.get(s);
		}
		
		if (s == null || s.length() == 0) return false;
		
		int i = 0; 
		int j = s.length() - 1;
		
		// only less than here is enough
		while (i < j) {
			if (s.charAt(i) != s.charAt(j)) {
				lookup.put(s, false);
				return false;
			}
			i++;
			j--;
		}
		
		lookup.put(s, true);
		return true;
	}

}
